//
// Source code recreated from a .class file by IntelliJ IDEA
// (powered by FernFlower decompiler)
//

package 力扣.题库.二分查找;

import java.util.Arrays;

public class demo_2389 {
    public demo_2389() {
    }

    public static void main(String[] args) {
        int[] nums = new int[]{736411, 184882, 914641, 37925, 214915};
        int[] queries = new int[]{331244, 273144, 118983, 118252, 305688, 718089, 665450};
        int[] answer = answerQueries(nums, queries);
        System.out.println(Arrays.toString(answer));
    }

    public static int[] answerQueries(int[] nums, int[] queries) {
        Arrays.sort(nums);
        long[] newNums = new long[nums.length];
        long sum = 0L;

        for(int i = 0; i < nums.length; ++i) {
            sum += (long)nums[i];
            newNums[i] = sum;
        }

        int[] answer = new int[queries.length];

        for(int i = 0; i < queries.length; ++i) {
            int l = 0;
            int r = newNums.length - 1;
            if ((long)queries[i] > newNums[r]) {
                l = r + 1;
            } else if ((long)queries[i] > newNums[l]) {
                while(l <= r) {
                    int mid = l + (r - l) / 2;
                    if (newNums[mid] > (long)queries[i]) {
                        r = mid - 1;
                    } else {
                        l = mid + 1;
                    }
                }
            }

            answer[i] = l;
        }

        return answer;
    }
}
